# -*- coding: utf-8 -*-
# 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列
# 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）
# 必须原地修改，只允许使用额外常数空间
# 以下是一些例子，输入位于左侧列，其相应输出位于右侧列
# 1,2,3 → 1,3,2
# 3,2,1 → 1,2,3
# 1,1,5 → 1,5,1

import sys;

# 算法可能超时就不再继续写了
# 具体思路：
# 1、总结序列
# 总结出的内容是，从序列左边开始，记录当前位数字大于右侧数字的数目
# 以[1,2,3,4]为例
# 数字以 4进制 3进制 2进制这样的数字递增
# 1,2,3,4 --- 0,0,0
# 1,2,4,3 --- 0,0,1
# 1,3,2,4 --- 0,1,0
# 1,3,4,2 --- 0,1,1
# 1,4,2,3 --- 0,2,0
# 1,4,3,2 --- 0,2,1
# -----------------
# 2,1,3,4 --- 1,0,0
# 2,1,4,3 --- 1,0,1
# 2,3,1,4 --- 1,1,0
# 2,3,4,1 --- 1,1,1
# 2,4,1,3 --- 1,2,0
# 2,4,3,1 --- 1,2,1
# ......
# class Solution(object):
#     def nextPermutation(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: void Do not return anything, modify nums in-place instead.
#         """
#         if len(nums) <= 1:
#             return;

#         large = [0] * (len(nums) - 1);
#         for i in xrange(0, len(nums) - 1):
#             for j in xrange(i, len(nums)):
#                 if nums[i] > nums[j]:
#                     large[i] += 1;

#         temp = nums[0:];

#         while True:
#             large[-1] += 1;
#             addtion = 0;
#             for i in xrange(0, len(large)):
#                 index = len(large) - 1 - i;
#                 if large[index] + addtion > i + 1:
#                     large[index] = 0;
#                     addtion = 1;
#                 else:
#                     large[index] = large[index] + addtion;
#                     break;

#             hash_map = {};
#             for num in temp:
#                 hash_map[num] = hash_map.get(num, 0) + 1;

#             if len(hash_map.keys()) == 1:
#                 return;

#             #根据 数字算出返回值
#             # ...一直写错，暂未完成

# # 通过汗颜呀！脑子成浆糊了
# # 算法说明
# # 2,2,7,5,4,3,2,2,1
# # 从右向左开始查找，查到一个元素右边有比他大的元素
# # 2,2,7,5,4,3,2,2,1
# #   #
# # 把和右边比他大的元素(最小的哪一个)交换
# # 2,2,7,5,4,3,2,2,1
# #   #       #
# # 2,3,7,5,4,2,2,2,1
# # 然后在对交换后的元素重新排序
# # 2,3,7,5,4,2,2,2,1
# #   #
# # 2,3,1,2,2,2,4,5,7
# class Solution(object):
#     def nextPermutation(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: void Do not return anything, modify nums in-place instead.
#         """
#         if len(nums) <= 1:
#             return;

#         for i in xrange(len(nums) - 2, -1, -1):
#             self.sortBE(nums, i + 1, len(nums));
#             for j in xrange(i + 1, len(nums)):
#                 if nums[j] <= nums[i]:
#                     continue;
#                 temp = nums[i];
#                 nums[i] = nums[j];
#                 nums[j] = temp;
#                 self.sortBE(nums, j, len(nums));
#                 return;
#         nums.sort();

#     def sortBE(self, nums, begin, end):
#         if end - begin <= 1 or end > len(nums):
#             return;
#         for i in xrange(begin, end):
#             for j in xrange(i + 1, end):
#                 if nums[j] < nums[i]:
#                     temp = nums[j];
#                     nums[j] = nums[i];
#                     nums[i] = temp;

# 查看官方的解答后
# 上方的解题步骤，可以简化为交换和反序2个部分
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2;
        while i >= 0 and nums[i + 1] <= nums[i]:
            i -= 1;
        if i>= 0:
            j = len(nums) - 1;
            while j > 0 and nums[j] <= nums[i]:
                j -= 1;
            self.swap(nums, i, j);
        self.reverse(nums, i + 1);

    def swap(self, nums, i, j):
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

    def reverse(self, nums, begin):
        end = len(nums) - 1;
        while begin < end:
            self.swap(nums, begin, end);
            begin += 1;
            end -= 1;



t = Solution();
nums = [3,2,1];
t.nextPermutation(nums);
print nums;